package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 87111
 * Date: 2025-09-03
 * Time: 13:51
 */
public class MySingleList {
    //节点类(静态内部类)
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    //创建一个链表
    public void createLinkedList() {
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        
        this.head = listNode1;
    }

    //头插法
    public void addFirst(int data){
        ListNode listnode = new ListNode(data);
        listnode.next = head;
        head = listnode;
    }
    //尾插法
    public void addLast(int data){
        ListNode listNode = new ListNode(data);
        if(head == null) {
            head = listNode;
        }
        //找到最后一个位置插入
        ListNode node = head;
        while(node != null) {
            if(node.next == null) {
                node.next = listNode;
                return;
            }
            node = node.next;
        }
    }

    //任意位置插⼊,第⼀个数据节点为0号下标
    public void addIndex(int index,int data){
        int len = size();
        if(index < 0 || index > len - 1) {
            return;
        }
        //头插法
        if(index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if(index == len - 1) {
            addLast(data);
            return;
        }
        //中间插入
        ListNode node = new ListNode(data);
        ListNode newHead = head;
        //获取插入位置的上一个节点
        ListNode cur = findBeginList(index);
        if(cur == null) {
            return;
        }
        node.next = cur.next;
        cur.next = node;
    }

    //找到插入位置的前一个节点
    private ListNode findBeginList(int index) {
        int len = size();
        if(index < 0 || index > len - 1) {
            return null;
        }
        ListNode node = head;
        int i = 0;
        while(i != index - 1) {
            node = node.next;
            i++;
        }
        return node;
    }

    //查找关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode node = head;
        while(node != null) {
            if(node.val == key) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    //删除第⼀次出现关键字为key的节点
    public void remove(int key){
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode val = findBeginNumList(key);
        if(val == null) {
            return;
        }
        ListNode cul = val.next.next;
        head.next = cul;
    }

    //查找关键字的前驱节点
    public ListNode findBeginNumList(int key) {
        if(head == null) {
            return null;
        }
        ListNode node = head;
        while(node.next != null) {
            if(node.next.val == key) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        //删除所有key节点
        ListNode cul = head;
        ListNode pex = cul.next;
        while(pex != null) {
            if(pex.val == key) {
                cul.next = pex.next;
                pex = pex.next;
            }else {
                cul = cul.next;
                pex = pex.next;
            }
        }
        //判断第一个元素是否需要删除
        if(head.val == key) {
            head = head.next;
        }
    }
    //得到单链表的⻓度
    public int size(){
        ListNode node = head;
        int listNum = 0;
        while(node != null) {
            listNum++;
            node = node.next;
        }
        return listNum;
    }
    public void clear() {
    }

    //打印链表
    public void display() {
        ListNode node = head;
        while(node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }

    //从指定节点打印链表
    public void display(ListNode listNode) {
        ListNode node = listNode;
        while(node != null) {
            System.out.println(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}
